//
//  linklist.swift
//  SetAndMap
//
//  Created by lhc on 2024/7/19.
//

import Foundation

class LinkListNode<E: Equatable> {
    var e: E?
    var next: LinkListNode?
    
    init(e: E? = nil, next: LinkListNode? = nil) {
        self.e = e
        self.next = next
    }
}

///  带一个虚拟头结点的链表
class LinkList<E: Equatable> {
    private var dummyNode: LinkListNode = LinkListNode<E>()
    private var size = 0
    
    /// 获取链表size
    func getSize() -> Int {
        return self.size
    }
    
    /// 判断链表是否为空
    func isEmpty() -> Bool {
        return self.size == 0
    }
    
    /// 插入元素
    ///
    /// element元素内容 index位置
    ///
    /// 如果index不合规会什么都不做
    func insetElement(_ element: E, index: Int) {
        // 比如有三个元素的链表0->1->2 不能插入的index是-1或者4，可以为3
        guard index >= 0 && index <= self.size else { return }
        
        var pre: LinkListNode<E>? = self.dummyNode
        for _ in 0..<index {
            pre = pre?.next
        }
        let node = LinkListNode(e: element, next: pre?.next)
        pre?.next = node
        self.size += 1
        
    }
    
    func addFirst(element: E) {
        self.insetElement(element, index: 0)
    }
    
    func addLast(element: E) {
        self.insetElement(element, index: self.size)
    }
    
    /// 删除对应index的元素
    func deleteByIndex(_ index: Int) -> E? {
        // 比如有三个元素0->1->2 size=3 可以删除0，1，2这三个index
        guard index >= 0 && index < self.size else {return nil}
        
        var pre: LinkListNode<E>? = self.dummyNode
        for _ in 0..<index {
            pre = pre?.next
        }
        let node = pre?.next
        pre?.next = node?.next
        node?.next = nil
        self.size -= 1
        return node?.e
    }
    
    func deleteFirst() -> E? {
        return self.deleteByIndex(0)
    }
    
    func deleteLast() -> E? {
        return self.deleteByIndex(self.size - 1)
    }
    
    /// 查看是否包含元素e
    func contains(e: E) -> Bool {
        var pre = self.dummyNode
        while pre.next != nil {
            if let element = pre.next?.e {
                if element == e {
                    return true
                }
            }
            pre = pre.next!
        }
        return false
    }
    
    /// 查找并删除元素
    func deleteElement(_ e: E) {
        var pre = self.dummyNode
        while pre.next != nil {
            if let element = pre.next?.e {
                if element == e {
                    let node = pre.next
                    pre.next = node?.next
                    node?.next = nil
                    self.size -= 1
                }
                
                pre = pre.next!
            }
        }
        // 到最后结点也没有对应元素
        
    }
    
    /// 返回链表遍历的对应数组
    func traversalList() -> [E] {
        var pre = self.dummyNode
        var resultList = [E]()
        while pre.next != nil {
            pre = pre.next!
            if let e = pre.e {
                resultList.append(e)
            }
        }
        return resultList
    }
}

